#
# memory cache, for ofs.
#
implement Cache;

include "sys.m";
	sys: Sys;
	fprint, sprint, pctl, millisec, DMDIR, write, nulldir, tokenize, fildes,
	QTDIR, FD, Dir, Qid: import sys;
include "names.m";
	names: Names;
	cleanname: import names;
include "string.m";
	str: String;
	splitstrl: import str;
include "styx.m";
	styx: Styx;
	unpackdir: import styx;
include "styxservers.m";
	Enotfound, Eexists: import Styxservers;
include "op.m";
include "error.m";
	err: Error;
	stderr, panic: import err;
include "cache.m";

cfsreqc: chan of (ref Creq, chan of ref Crep);
ncachedfiles := 0;
coherencylag := 0;

init(s: Styx, nil: string, lag: int): string
{
	sys = load Sys Sys->PATH;
	err = load Error Error->PATH;
	err->init();
	names = load Names Names->PATH;
	str = load String String->PATH;
	if (sys == nil || names == nil || str == nil)
		return "load failed in cache";
		styx = s;
	coherencylag = lag;
	cfsreqc = chan of (ref Creq, chan of ref Crep);
	spawn cfsproc(cfsreqc);
	return nil;
}

term()
{
	cfsreqc <-= (nil, nil);
}

Creq.text(r: self ref Creq) : string
{
	if (r == nil)
		return "nullreq";
	pick c:= r {
	Stat =>	return "stat";
	Info => return "info";
	Readdir => return "readdir";
	Flush => return "flush";
	Remove => return "remove";
	Valid => return "valid(" + c.name + ")";
	Validate => return "validate(" + c.name + ")";
	Invalidate => return "invalidate(" + c.name + ")";
	Create => return "create(" + c.name + ")";
	Walk1 => return "walk1";
	Wstat => return "wstat";
	Pread => return "pread";
	Pwrite => return "pwrite";
	* => return "unknown";
	}
}

cacherpc(r: ref Creq) : ref Crep
{
	c := chan of ref Crep;
	cfsreqc <-= (r, c);
	return <- c;
}

cfsproc(cfsreqc : chan of (ref Creq, chan of ref Crep))
{
	fstab := array[211] of ref Cfile;	# use a prime number 

	rootd := ref nulldir;
	rootd.name = "/";
	rootd.uid = rootd.gid = rootd.muid = "sys";
	rootd.qid = Qid(big 0, 0, QTDIR);
	root := fscreate(fstab, nil, rootd);
	if (root == nil)
		panic("cache: can't create root");
	if (debug)
		fprint(stderr, "cache: new: %s\n", fs2text(fstab, root));
	for (;;){
		(r, rc) := <- cfsreqc;
		if (r == nil){
			if (debug) fprint(stderr, "mcache: stop\n");
			break;
		}
		if (debug > 1)
			fprint(stderr, "%08d cfsreq: %s: ", millisec(), r.text());
		f := r.f;
		if (f == nil)
			f = findfile(fstab, r.qid);
		if (debug > 1 && f == nil)
			fprint(stderr, "cache: no file for request %s, qid %bx\n", r.text(), r.qid);
		if (f != nil && f.d == nil)
			panic(sprint("cache: nil dir for file 16r%bx", r.qid));
		if (debug > 1)
			fprint(stderr, "%s\n", fs2text(fstab, f));
		pick rr := r {
		Dump =>
			dump(fstab, root, 0, "cfs tab:\n");
			rc <-= ref Crep.Dump(nil, nil);
		Stat =>
			if (f == nil)
				rc <-= ref Crep.Stat("invalid", nil, nil);
			else
				rc <-= ref Crep.Stat(nil, f, ref *f.d);
		Info =>
			if (f == nil)
				rc <-=ref Crep.Info("invalid", nil, nil, nil, 0);
			else {
				dirty := (f.dirtyd  || f.created);
				rc <-= ref Crep.Info(nil, f, fsgetpath(fstab, f), f.d, dirty);
			}
		Flush =>
			if (f == nil)
				rc <-= ref Crep.Flush("invalid", nil, nil, nil, 0);
			else {
				rd : ref Sys->Dir;
				if (f.dirtyd)
					rd = f.d;
				rep := ref Crep.Flush(nil, f, fsgetpath(fstab, f), rd, f.created);
				f.created = f.dirtyd = 0;
				f.oldname = nil;
				rc <-= rep;
			}
		Create =>
			if (f == nil)
				rc <-= ref Crep.Create("invalid", nil, nil);
			else {
				f = fswalkorcreate(fstab, f, rr.name, rr.d);
				f.data = rr.data;
				f.created = f.dirtyd = 1;
				rc <-= ref Crep.Create(nil, f, ref *f.d);
			}
		Valid =>
			if (f == nil)
				rc <-= ref Crep.Validate("invalid", nil, nil);
			else {
				(nels, els) := tokenize(rr.name, "/");
				for (i := 0 ; f != nil && i < nels -1; i++){	# find or fake entry
					f = fswalk(fstab, f, hd els);
					els = tl els;
				}
				sf := f;
				if (f != nil && els != nil)
					sf = fswalk(fstab, f, hd els);
				now := millisec();
				# security: an empty directory is not considered valid and we say invalid
				# so the caller re-reads. Otherwise, reading the parent leads the directory
				# valid, although we only have its stat.
				if (sf == nil && f != nil && f.dirread && now - f.time < coherencylag)
					rc <-= ref Crep.Valid(nil, nil, nil, "file does not exist");
				else if (sf != nil && f != nil && now - f.time < coherencylag &&
					(!(sf.d.qid.qtype&QTDIR) || sf.dirread) )
					rc <-= ref Crep.Valid(nil, sf, sf.d, nil);
				else
					rc <-= ref Crep.Valid("invalid", nil, nil, nil);
			}
		Validate =>
			if (f == nil)
				rc <-= ref Crep.Validate("invalid", nil, nil);
			else {
				(nels, els) := tokenize(rr.name, "/");
				for (i := 0 ; i < nels -1; i++){	# find or fake entry
					f = fswalkorcreate(fstab, f, hd els, nil);
					els = tl els;
				}
				# els may be nil if f is the result of walk (eg. root)
				if (els != nil)
					f = fswalkorcreate(fstab, f, hd els, rr.d);
				if (rr.d != nil){
					if (f.serverqid.path != big 0 && f.serverqid.path != big ~0)
					if (f.serverqid.path != rr.d.qid.path || f.serverqid.vers != rr.d.qid.vers)
					if (!f.created)
						f.data = array[0] of byte;
					fswstat(fstab, f, rr.d);
				}
				if (f.d.qid.qtype&QTDIR)
					updatedirdata(fstab, f, rr.data);
				else if (!f.dirtyd && !f.created)
					f.data = rr.data;
				f.time = millisec();
				rc <-= ref Crep.Validate(nil, f, ref *f.d);
			}
		Invalidate =>
			if (f != nil){
				(nels, els) := tokenize(rr.name, "/");
				for (i := 0; f != nil && i < nels ; i++){
					f = fswalk(fstab, f, hd els);
					els = tl els;
				}
				if (f != nil && f != root && !f.dirtyd && !f.created){
					if (debug)
						fprint(stderr, "cache: invalidate %bx %s\n", f.d.qid.path, f.d.name);
					fsremove(fstab, f.d.qid.path);
					f.d = nil;
				}
			}
			rc <-= ref Crep.Invalidate(nil, nil);
		Remove =>
			if (f == nil)
				rc <-= ref Crep.Remove("invalid", nil, nil);
			else {
				name := fsgetpath(fstab, f);
				fsremove(fstab, f.d.qid.path);
				f.d = nil;
				rc <-= ref Crep.Remove(nil, nil, name);
			}
		Walk1 =>
			if (f == nil)
				rc <-= ref Crep.Walk1("invalid", nil, nil);
			else {
				f = fswalk(fstab, f, rr.name);
				if (f == nil)
					rc <-= ref Crep.Walk1("invalid", nil, nil);
				else
					rc <-= ref Crep.Walk1(nil, f, ref *f.d);
			}
		Readdir =>
			if (f == nil)
				rc <-= ref Crep.Readdir("invalid", nil, nil);
			else
				rc <-= ref Crep.Readdir(nil, f, fschilds(f, rr.off, rr.cnt));
		Wstat =>
			if (f == nil)
				rc <-= ref Crep.Wstat("invalid", nil, nil);
			else {
				e := fswstat(fstab, f, rr.d);
				if (e == nil && f.d.length == big 0 && (f.d.qid.qtype&QTDIR)==0){
					f.data = array[0] of byte;
					f.created  |= rr.dirties;	# to truncate it
				}
				if (e == nil)
					f.dirtyd  |= rr.dirties;		# update new length
				if (f.dirtyd)
					f.time = 0;
				rc <-= ref Crep.Wstat(e, f, rr.d);
			}
		Pread =>
			# we cache prefixes only
			if (f == nil)
				rc <-= ref Crep.Pread("invalid", nil, nil, nil);
			else if (rr.off >= f.d.length && f.d.length > big 0)
				rc <-= ref Crep.Pread(nil, f, nil, array[0] of byte);
			else if (rr.off < big len f.data){
				n := int rr.off + rr.cnt;
				if (n >  len f.data)
					n = len f.data;
				rc <-= ref Crep.Pread(nil, f, nil, f.data[int rr.off:n]);
			} else
				rc <-= ref Crep.Pread("not cached", f, fsgetpath(fstab, f), nil);
		Pwrite =>
			# This is write-through.
			# We update data, but the caller must do a Put.
			if (f == nil)
				rc <-= ref Crep.Pwrite("invalid", nil, nil);
			else {
				if (rr.off <= big len f.data){
					if (int rr.off + len rr.data > MAXCACHED){
						f.data = f.data[0:int rr.off];
					} else {
						off := int rr.off;
						ndata := array[off + len rr.data] of byte;
						ndata[0:] = f.data[0:off];
						ndata[off:] = rr.data;
						f.data = ndata;
						if (f.d.length < big len f.data)
							f.d.length = big len f.data;
					}
				}
				if (rr.dirties)
					f.time = 0;
				rc <-= ref Crep.Pwrite (nil, f, fsgetpath(fstab, f));
			}
		}
	}
}

updatedirdata(tab: array of ref Cfile, f: ref Cfile, data : array of byte)
{
	sons, l : list of  ref Dir;
	gonesons : list of big;
	tot := n:= 0;
	d : ref Dir;
	xd : Dir;
	fh: ref Cfile;

	f.dirread = 1;
	# 1. unpack.
	do {
		(n, xd) = unpackdir(data[tot:]);
		tot += n;
		if (n >= 0)
			sons = ref xd :: sons;
	} while (n > 0 && tot < len data);

	# 2. update changed ones; record gone ones.
	gonesons = nil;
	for(fh = f.child; fh != nil; fh = fh.sibling){
		if (fh.serverqid.path == big 0){
			# search by name; faked
			for (l = sons; l != nil && (hd l).name != fh.d.name ; l = tl l)
				;
		} else {
			# search by qid
			for (l = sons; l != nil && (hd l).qid.path != fh.serverqid.path ; l = tl l)
				;
		}
		if (l != nil){
			q := fh.d.qid.path;	# we invent our own qids
			fh.d = ref *(hd l);
			fh.serverqid = fh.d.qid;
			fh.d.qid.path = q;
		} else
			# must keep files just created (they may be not yet reported by the server)
			if (!fh.created)
				gonesons = fh.d.qid.path :: gonesons;
	}

	# 3. remove gone ones
	while(gonesons != nil){
		if (debug)
			fprint(stderr, "cache: readdir: invalidate %bx \n", hd gonesons);
		fsremove(tab, hd gonesons);
		gonesons = tl gonesons;
	}

	# 4. add new ones
	for(l = sons; l != nil; l = tl l){
		d = hd l;
		sq := d.qid.path;
		for (fh = f.child; fh != nil && fh.serverqid.path != sq; fh = fh.sibling)
			;
		if (fh == nil){
			d.qid.path = ++qseq;
			fh = fscreate(tab, f, d);
			if (fh == nil){
				# this happens for files bound twice or more in the same dir
				# the file is already cached, ignore.
				--qseq;
			} else {
				fh.serverqid =  Qid(sq, d.qid.vers, d.qid.qtype);
				if (debug)
					fprint(stderr, "cache: new: %s\n", fs2text(tab, fh));
			}
		}
	}
}

hashfn(q: big, n: int): int
{
	h := int (q % big n);
	if (h < 0)
		h += n;
	return h;
}

findfile(tab: array of ref Cfile, q: big): ref Cfile
{
	for (fh := tab[hashfn(q, len tab)]; fh != nil; fh = fh.hash)
		if (fh.d.qid.path == q)
			return fh;
	return nil;
}

fsgetpath(tab: array of ref Cfile, fh: ref Cfile): string
{
	if (fh == nil)
		panic("fsgetpath: nil fh");
	if (fh.d == nil)
		panic("fsgetpath: nil d");
	s : string;
	if (fh.parentqid == fh.d.qid.path)
		return "/";
	for(;;) {
		if (fh.d == nil)
			panic("fsgetpath:null dir");
		if (s == nil){
			if (fh.oldname != nil)
				s = fh.oldname;
			else
				s = fh.d.name;
		} else if (fh.parentqid == fh.d.qid.path)
			return "/" + s;
		else {
			if (fh.oldname != nil)
				s = fh.oldname + "/" + s;
			else
				s = fh.d.name + "/" + s;
		}
		fh = findfile(tab, fh.parentqid);
		if (fh == nil)
			panic("fsgetpath:parent not in table");
	}
	return nil;
}

fswalk(tab: array of ref Cfile, fh: ref Cfile, name: string): ref Cfile
{
	if (name == "..")
		return findfile(tab, fh.parentqid);
	for (fh = fh.child; fh != nil; fh = fh.sibling)
		if (fh.d.name == name)
			return fh;
	return nil;
}

qseq := big 16r6b60000000000000;

fswalkorcreate(tab: array of ref Cfile, fh: ref Cfile, name: string, d: ref Dir): ref Cfile
{
	f := fswalk(tab, fh, name);
	if (f == nil){
		if (d == nil){
			d = ref *fh.d;
			d.qid.path = ++qseq;
			d.qid.qtype = QTDIR;
			d.qid.vers = 0;
			d.name = name;
		} else {
			d.qid.path = ++qseq;	# we use our own qids.
			d.name = name;		# even when d.qid is ok.
			if (d.mode&DMDIR)
				d.qid.qtype |= QTDIR;
		}
		f = fscreate(tab, fh, d);
		if (f == nil)
			panic(sprint("walkorcreate: create: %s at %s q %bx\n", name, fh.d.name, d.qid.path));
		else
			if (debug)
				fprint(stderr, "cache: added: %s\n", fs2text(tab, f));
	}
	if (f == nil)
		panic(sprint("walkorcreate: nil f for name %s", name));
	return f;
}

fschilds(f: ref Cfile, off, cnt: int) : list of Sys->Dir
{
	fh := f.child;
	while(off > 0 && fh != nil){
		off--;
		fh = fh.sibling;
	}
	l : list of Sys->Dir;
	l = nil;
	while(cnt > 0 && fh != nil){
		cnt--;
		l = *fh.d :: l;
		fh = fh.sibling;
	}
	return l;
}


fsremove(tab: array of ref Cfile, q: big): string
{
	prev: ref Cfile;

	# remove from hash table
	slot := hashfn(q, len tab);
	for (fh := tab[slot]; fh != nil; fh = fh.hash) {
		if (fh.d.qid.path == q)
			break;
		prev = fh;
	}
	if (fh == nil)
		return Enotfound;
	if (prev == nil)
		tab[slot] = fh.hash;
	else
		prev.hash = fh.hash;
	fh.hash = nil;

	# remove from parent's children
	parent := findfile(tab, fh.parentqid);
	if (parent != nil) {
		prev = nil;
		for (sfh := parent.child; sfh != nil; sfh = sfh.sibling) {
			if (sfh == fh)
				break;
			prev = sfh;
		}
		if (sfh == nil)
			panic("child not found in parent");
		if (prev == nil)
			parent.child = fh.sibling;
		else
			prev.sibling = fh.sibling;
	}
	fh.sibling = nil;

	# now remove any descendents
	sibling: ref Cfile;
	for (sfh := fh.child; sfh != nil; sfh = sibling) {
		sibling = sfh.sibling;
		sfh.parentqid = sfh.d.qid.path;		# make sure it doesn't disrupt things.
		fsremove(tab, sfh.d.qid.path);
	}
	ncachedfiles--;
	return nil;
}

fscreate(tab: array of ref Cfile, parent: ref Cfile, d: ref Sys->Dir): ref Cfile
{
	if (findfile(tab, d.qid.path) != nil){
		fprint(stderr, "fscreate: qid already exists: %bx\n", d.qid.path);
		return nil;
	}
	fh: ref Cfile;
	if (parent == nil)
		fh = ref Cfile(~0, d, nil, 0, 0, 0, nil, d.qid.path, Qid(big 0, 0, d.qid.qtype), nil, nil, nil, 0);
	else {
		if (fswalk(tab, parent, d.name) != nil)
			return nil;
		fh = ref Cfile(~0, d, nil, 0, 0, 0, nil, parent.d.qid.path, Qid(big 0, 0, d.qid.qtype), nil, nil, nil, 0);
		fh.sibling = parent.child;
		parent.child = fh;
	}
	slot := hashfn(d.qid.path, len tab);
	fh.hash = tab[slot];
	tab[slot] = fh;
	ncachedfiles++;
	return fh;
}

fswstat(tab: array of ref Cfile, fh : ref Cfile, d: ref Sys->Dir): string
{
	q := fh.d.qid.path;
	# if renaming a file, check for duplicates
	if (d.name != nil && d.name != fh.d.name) {
		parent := findfile(tab, fh.parentqid);
		if (parent != nil && parent != fh && fswalk(tab, parent, d.name) != nil)
			return Eexists;
		fh.oldname = fh.d.name;
		parent.time = 0;	# invalidate
		fh.time = 0;		# invalidate
	}
	d = applydir(d, fh.d);
	if (fh.data != nil && d.length < big len fh.data)
	if ((d.qid.qtype&QTDIR) == 0)
		fh.data = fh.data[0:int d.length];
	fh.d = d;
	fh.d.qid.path = q;		# ensure the qid can't be changed
	return nil;
}

applydir(d: ref Sys->Dir, onto: ref Sys->Dir): ref Sys->Dir
{
	if (d.name != nil)
		onto.name = d.name;
	if (d.uid != nil)
		onto.uid = d.uid;
	if (d.gid != nil)
		onto.gid = d.gid;
	if (d.muid != nil)
		onto.muid = d.muid;
	if (d.qid.vers != ~0)
		onto.qid.vers = d.qid.vers;
	if (d.qid.qtype != ~0)
		onto.qid.qtype = d.qid.qtype;
	if (d.qid.vers != ~0)
		onto.qid.vers = d.qid.vers;
	if (d.mode != ~0)
		onto.mode = d.mode;
	if (d.atime != ~0)
		onto.atime = d.atime;
	if (d.mtime != ~0)
		onto.mtime = d.mtime;
	if (d.length != ~big 0)
		onto.length = d.length;
	if (d.dtype != ~0)
		onto.dtype = d.dtype;
	if (d.dev != ~0)
		onto.dev = d.dev;
	return onto;
}

qid2text(q: Sys->Qid): string
{
	return sys->sprint("%.2ubx:%.2ux:%.2ux", q.path, q.vers, q.qtype);
}

dir2text(d: ref Sys->Dir): string
{
	return sys->sprint("[\"%s\"  %s 8r%uo %bd]",
		d.uid, qid2text(d.qid), d.mode, d.length);
}

fs2text(tab: array of ref Cfile, fh: ref Cfile): string
{
	if (fh == nil)
		return "nil file";
	return sprint(" \"%s\" %s\tc%d s%d sq=%s %d bytes\n",
		fsgetpath(tab, fh), dir2text(fh.d), fh.created, fh.dirtyd,
		qid2text(fh.serverqid), len fh.data);
}

dump(tab: array of ref Cfile, f: ref Cfile, t: int, pref: string)
{
	tabs := "\t\t\t\t\t\t\t\t\t\t";
	s := "";
	if (pref != nil){
		s = pref + sprint("(%d files)\n", ncachedfiles);
		pref = nil;
	}
	ts := tabs[0:t];
	s += ts + fs2text(tab, f);
	a:= array of byte s;
	write(stderr, a, len a);
	for (fh := f.child; fh != nil; fh = fh.sibling)
		dump(tab, fh, t+1, nil);
}
